package heima.test.demo2;

import java.util.*;

public class Main {

    public static void main(String[] args){
        // 生成囚犯
        List<Integer> id_sets = new ArrayList<>(200);
        List<Integer> ids = new LinkedList<>();
        Map<Integer, Integer> id2pos = new HashMap<>();
        for(int i=0; i<200; i++){
            id_sets.add(i+1);
        }

        Random random = new Random();
        for(int i=0; i<100; i++){
            int index = random.nextInt(200-i);
            int id = id_sets.get(index);
            ids.add(id);
            id2pos.put(id, i+1);
            id_sets.remove(index);
        }
        System.out.println("囚犯编号："+ ids);
        int step = 0;
        while(ids.size() > 1){
            Iterator<Integer> iter = ids.iterator();
            int count = 0;
            while(iter.hasNext()){
                count ++;
                iter.next();
                if(count % 2 ==1) iter.remove();
            }
            step ++;
            System.out.println("第" + step + "轮剩余囚犯："+ids);
        }

        System.out.println("幸存者id为" + ids.getFirst() +", 初始位置为" + id2pos.get(ids.getFirst()));


    }
}
